package problems;

import utils.beans.ListNode;

import java.util.*;

/**
 * @author habitplus
 * @since 2023/3/18 9:51
 */
public class Main {
    //    public int solution(int[] arr, int k) {
//        if (k < 1) return 0;
//        int ret = 0;
//        int n = arr.length;
//        int[] cntMap = new int[2001];
//        int total = 0;
//        int pre = 0;
//        for (int i = 0; i < n; ++i) {
//            ++cntMap[arr[i]];
//            if (cntMap[arr[i]] == 1) ++total;
//
//            if (total > k) {
//                ret = Math.max(i - pre, ret);
//                while (pre < i) {
//                    --cntMap[arr[pre]];
//                    if (cntMap[arr[pre]] == 0) {
//                        ++pre;
//                        break;
//                    }
//                    ++pre;
//                }
//            }
//        }
//
//        return Math.max(ret, n - pre);
//    }

//    public int solution(int[] arr, int k) {
//        if (k < 1) return 0;
//        int ret = 0;
//        int n = arr.length;
//        int[] cntMap = new int[2001];
//        int total;
//        for (int i = 0; i < n; ++i) {
////            int[] cntMap = new int[2001];
//            Arrays.fill(cntMap, 0);
//            total = 0;
//            for (int j = i; j <= n; ++j) {
//                if (j == n) {
//                    ret = Math.max(j - i, ret);
//                    break;
//                }
//                ++cntMap[arr[j]];
//                if (cntMap[arr[j]] == 1) ++total;
//                if (total > k) {
//                    ret = Math.max(j - i, ret);
//                    break;
//                }
//            }
//        }
//
//        return ret;
//    }

    public String solution(String s) {
        if (s == null || s.length() < 1) return "";
        if (s.length() < 2) return "a";
        char[] chs = s.toCharArray();
        int n = chs.length;
        int l = 0;
        int r = chs.length - 1;
        int modCount = 0;
        int[] pos = new int[2];
        while (l < r) {
            if (chs[l] != chs[r]) {
                pos[modCount++] = l;
            }
//            if (modCount >= 2) break;
            ++l;
            --r;
        }

        if (modCount >= 2) {
            for (int i = 0; i < 2; ++i) {
                int ii = pos[i];
                if (chs[ii] > chs[n - 1 - ii]) {
                    chs[ii] = chs[n - 1 - ii];
                } else {
                    chs[n - 1 - ii] = chs[ii];
                }
            }
        } else if (modCount == 1) {
            int j = pos[0];
            if (n % 2 == 0) {
                // 偶数
                chs[j] = 'a';
                chs[n - 1 - j] = 'a';
            } else {
                // 奇数
                if (chs[j] == 'a' || chs[n - 1 - j] == 'a') {
                    chs[j] = 'a';
                    chs[n - 1 - j] = 'a';
                    chs[n / 2] = 'a';
                } else {
                    chs[j] = 'a';
                    chs[n - 1 - j] = 'a';
                }
            }
        } else {
            int j = 0;
            while (j < n / 2) {
                if (chs[j] != 'a') {
                    chs[j] = 'a';
                    chs[n - 1 - j] = 'a';
                    break;
                }
                ++j;
            }

            if (j == n / 2) chs[n / 2] = 'a';
        }

        return new String(chs);
    }

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        String s = sc.nextLine();
//
//        System.out.println(new Main().solution(s));

        int r = (int) 1e9;
        int l = 0;
        int target = 1;
        int round = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            System.out.printf("第 %d 次 -> mid=%d%n", ++round, mid);
            if (target == mid) {
                System.out.println("\n\n Found!");
                break;
            } else if (target > mid) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

    }


    public ListNode reverseList(ListNode head) {
        // write code here
        if (head == null || head.next == null)
            return head;
        ListNode pre = null;
        ListNode t;
        while (head != null) {
            t = head.next;
            head.next = pre;
            pre = head;
            head = t;
        }

        return pre;
    }

    public boolean canFinish(int n, int[][] pres) {
        if (n < 1 || pres == null || pres.length < 1)
            return true;

        // 节点入度
        int[] inDegs = new int[n];
        // 节点的出边
        List<Integer>[] out = new List[n];

        for (int i = 0; i < n; ++i)
            out[i] = new ArrayList<>();


        for (int[] p : pres) {
            if (p[0] == p[1])
                return false;
            ++inDegs[p[0]];
            out[p[1]].add(p[0]);
        }

        Queue<Integer> que = new LinkedList<>();
        for (int i = 0; i < n; ++i) {
            if (inDegs[i] < 1)
                que.offer(i);
        }

        // 已经学习的课程
        int studied = 0;
        while (!que.isEmpty()) {
            int cur = que.poll();
            ++studied;
            for (int nxt : out[cur]) {
                --inDegs[nxt];
                if (inDegs[nxt] == 0) {
                    que.offer(nxt);
                }
            }
        }

        return studied == n;
    }

}
